package _interview100;

import java.util.ArrayList;
import java.util.List;

/**
 * 118. 杨辉三角
 */
public class No118 {
    private int numRows;
    private List<List<Integer>> ans;

    public List<List<Integer>> generate(int numRows) {
        this.numRows = numRows;
        ans = new ArrayList<>();

        dfs(List.of(1));
        return ans;
    }

    private void dfs(List<Integer> preList) {
        ans.add(preList);
        if (preList.size() == numRows) return;
        ArrayList<Integer> curList = new ArrayList<>();
        curList.add(1);
        for (int i = 0; i < preList.size() - 1; i++) {
            curList.add(preList.get(i) + preList.get(i + 1));
        }
        curList.add(1);
        dfs(curList);
    }
}
